מטריצה דלילה

מטריצה דלילה (באנגלית: Sparse Matrix) היא מטריצה שמרבית איבריה בעלי ערך אפס. למטריצה דלילה חשיבות ליעילותם של חישובים נומריים שונים שבהם ניתן להסתפק במעבר רק על איברי המטריצה שאינם בעלי ערך אפס ולקומפקטיות באחסון מידע בינארי. ישנם מספר פורמטים לאחסון מטריצה דלילה, כאשר ניתן להבדיל בין פורמטים תומכי עדכון יעיל של המטריצה, כגון: DOK,‏ LIL,‏ COO ופורמטים התומכים בפעולות מטריצה יעילות (כפל מטריצות, שחלוף וכו'), כגון: CSR ו-CSC. לרוב נעשה שימוש בפורמטים תומכי פעולה יעילה.

מוטיבציה

המימוש הטריוויאלי של מבנה נתונים המייצג מטריצה מסדר m על n, (כאשר n,m הם מספרים טבעיים) הוא מערך דו־ממדי בעל ממדים מתאימים n,m כאשר כל תא $\ a_{ij}$ במטריצה נגיש במערך באמצעות האינדקסים j,i. כדי לייצג מטריצה מסדר m×n בזיכרון נדרש להקצות זיכרון בגודל לפחות m×n פעמים גודל האיבר הבודד. אם נשתמש במימוש הטריוויאלי של מטריצה בעבור מטריצות מסדרים גבוהים בהן רוב התאים מכילים את הערך 0, נתקל בבעיית זיכרון, למשל: בעבור מטריצה מסדר 10,000×10,000 המכילה מספרים שלמים נצטרך 4byte × 10,000² = 381.5MB, בעבור מטריצה מסדר 100,000×100,000 המכילה מספרים שלמים נצטרך כבר 37.25GB - מספרים מוגזמים לכל הדעות; לכן, בעבור מטריצות מהסוג הנ"ל, אם נאחסן רק את הערכים השונים מ-0 נצטרך כמות זיכרון קטנה הרבה יותר והיא $O(nz)$, כאשר nz מייצג את מספר הערכים השונים מ-0 (nz - Non Zero).

בהרבה מטריצות מסדרים גבוהים שכאלו ויותר שמרבית תאיהן מכילות את הערך 0 נתקל בעת פתרון משוואות דיפרנציאליות חלקיות.

כאשר מדברים על מטריצה דלילה מדברים על מטריצה בה רוב התאים מכילים את הערך 0, אך ניתן (לרוב לא רצוי) להחיל את העיקרון על כל ערך קבוע. יכולת זו לא נתמכת באופן מוחלט מאחר שיש לערך השפעה על האופן בו מחשבים פעולות על מטריצות דלילות, אך בעבור מטריצה A וערך c קבוע A - c = B כאשר B היא מטריצה בה הערך 0 החליף את ערכי c כנדרש.

אחסון מטריצה דלילה

נחלק את השיטות השונות לאחסון מטריצה דלילה לשתי קבוצות:

1. שינוי יעיל של המטריצה.
2. פעולות יעילות על המטריצה.

בהרבה מקרים ההבדל בביצועים הוא משמעותי ויהיה צורך לבנות את המטריצה הדלילה כמטריצה מהקבוצה הראשונה ובהמשך להמיר אותה למטריצה מהקבוצה השנייה במקום לבחור בשיטה אחת.
נדגים את השיטות המצוינות למטה באמצעות המטריצה הבאה:

[ 0 0 1 0 ]
[ 3 2 0 0 ]
[ 0 4 0 0 ]
[ 0 0 5 0 ]

שיטות המאפשרות שינוי יעיל של המטריצה

(Dictionary of keys (DOK

DOK היא שיטה לייצוג התאים השונים מ-0 במטריצה כמיפוי זוג סדור המכיל את המיקום של התא במטריצה הקונקרטית המקבילה לערך באמצעות מפה.

row,col]->1]
[0,1]->1
[1,2]->2
[1,3]->3
[2,2]->4
[3,1]->5

(List of lists (LIL

LIL היא שיטה לייצוג התאים השונים מ-0 במטריצה באמצעות הקצאת רשימה עבור כל שורה, כאשר כל תא בשורה מאחסן ערך ומספר עמודה בה היה התא במטריצה הקונקרטית המקבילה.

[row->[val,col
0->[1,1]
1->[2,2]->[3,3]
2->[4,2]
3->[5,1]

(Coordinate list (COO

COO היא שיטה לייצוג התאים השונים מ-0 במטריצה כמערך של שלישיות סדורות המכילות את המיקום והערך של תא במטריצה הקונקרטית המקבילה.

[5, 4, 3, 2, 1] :val
[3, 2, 1, 1, 0] :row
[1, 2, 3, 2, 1] :col

שיטות המאפשרות פעולות יעילות על המטריצה

אם יש צורך לבנות את המטריצה הדלילה באופן דינאמי, יש לבנותה עם אחת השיטות DOK,LIL,COO ואז להמירה לאחת מהשיטות הבאות:

Yale format

שיטת Yale מאחסנת מטריצה דלילה מסדר m×n בתצורת שורה (משמע ע"פ שורה, שורה ואז טור) באמצעות 3 מערכים, A, IA, JA.
A, בגודל nz, הוא המערך המכיל את הערכים השונים מאפס סדורים לפי השורה והטור (משמאל לימין ואז מלמעלה למטה).
IA, בגודל m+1 (מספר השורות + 1), מכיל את מספר האינדקס המכיל את הערך הראשון השונה מאפס במערך A בשורה שהאינדקס שלה הוא אינדקס התא הנוכחי.
JA, בגודל nz, הוא המערך המכיל את מספרי הטור של כל אחד מהערכים השונים מאפס לפי סדרם ב-A.

[A: [1, 2, 3, 4, 5
[IA: [0, 1, 3, 4, 5
[JA: [1, 2, 3, 2, 1

הערה: השיטה הנ"ל חוסכת מקום רק כאשר מתקיים 2/(nz < (m(n - 1) - 1.

(Compressed sparse row (CSR or CRS

שיטת CSR למעשה זהה לשיטת Yale, מלבד שמערך הטורים מאוחסן לפני מערך השורות, משמע (val, col_ind, row_ptr). שיטה זו יעילה עבור פעולות ארתמטיות, גזירת שורות ספציפיות ומכפלת מטריצה-וקטור.

(Compressed sparse column (CSC or CCS

שיטת CSC דומה לCSR, ההבדל טמון בכך שבעוד CSR היא בתצורת שורה, CSC היא בתצורת טור, משמע במקום לשמור מערך המכיל מצביעים אל תחילת כל שורה במערך הערכים, יהיה מערך המכיל מצביעים אל תחילת כל טור במערך הערכים (ובהתאמה המערך הנוסף המייצג את הקורדינאטה הנוספת). בשיטה זו אופן מילוי המערך A (מערך הערכים) יהיה מלמעלה למטה ואז מימין לשמאל. שיטה זו יעילה עבור פעולות ארתמטיות, גזירת שורות ספציפיות ומכפלת מטריצה-וקטור.

Code Frameworks

++C++: SparseLib
‏Python: SciPy

Ruby: SciRuby

קישורים חיצוניים

מדיה וקבצים בנושא מטריצה דלילה בוויקישיתוף

• מטריצה דלילה, באתר MathWorld (באנגלית)